
#include "bintree.h"

struct Tree
{
	void *value;
	Tree *lchild;
	Tree *rchild;
};

Tree* Init()
{
	Tree *tree = (Tree*) malloc(sizeof(Tree));
	tree->value = NULL;
	tree->lchild = NULL;
	tree->rchild = NULL;
	return tree;
}

int Insert(void* obj, Tree* tree, int(*cmp)(void*, void*))
{
	if(tree->value == NULL)
	{
		tree->value = obj;
		return 1;
	}
	else
	{
		//compare value of obj with value of tree
		if(cmp(obj, tree->value) == -1 || cmp(obj, tree->value) == 0)
		{
			//check if lchild is NULL
			if(tree->lchild == NULL)
			{
				//insert obj as left child
				tree->lchild = Init();
				tree->lchild->value = obj;
				return 1;
			}
			else
			{
				return Insert(obj, tree->lchild, cmp);
			}
		}
		else if(cmp(obj, tree->value) == 1)
		{
			//check if rchild is NULL
			if(tree->rchild == NULL)
			{
				//insert obj as right child
				tree->rchild = Init();
				tree->rchild->value = obj;
				return 1;
			}
			else
			{
				return Insert(obj, tree->rchild, cmp);
			}
		}
	}
	
	return 0;
}

int Remove( Tree *tree, int (*hit)( void *))
{
	if(hit(tree->value) != 0)
	{
		Delete(tree);
	}
	else
	{
		if(tree->lchild != NULL)
			Remove(tree->lchild, hit);
		if(tree->rchild != NULL)
			Remove(tree->rchild, hit);
	}
	return 1;
}

void *Find( Tree *tree, int (*hit)( void *))
{
	void *obj = NULL;
	if(hit(tree->value) != 0)
	{
		obj = tree->value;
		return obj;
	}
	else
	{
		if(tree->lchild != NULL)
		{
			obj = Find(tree->lchild, hit);
			if(obj != NULL)
				return obj;
		}
		if(tree->rchild != NULL)
		{
			obj = Find(tree->rchild, hit);
			return obj;
		}
	}
}

void Delete(Tree *tree)
{
	if(tree->lchild == NULL && tree->rchild == NULL)
		free(tree);
	else
	{
		if(tree->lchild != NULL)
		{
			Delete(tree->lchild);
		}
		if(tree->rchild != NULL)
		{
			Delete(tree->rchild);
		}
		free(tree);
	}
	
}

void PrintTree(Tree *tree, void (*toString)(void*))
{
	toString(tree->value);
	if(tree->lchild || tree->rchild)
	{
		printf("(");
		if(tree->lchild)
		{
			printf("leftchild = ");
			PrintTree(tree->lchild, toString);
			printf(", ");
		}
		if(tree->rchild)
		{
			printf("rightchild = ");
			PrintTree(tree->rchild, toString);
			
		}
		printf(")");
	}
		
}